package com.LeeCode;

/**
 * 新 21 点
 */

public class Code837 {
    public static void main(String[] args) {
        int n = 21, k = 17, maxPts = 10;
        System.out.println(new Code837().new21Game(n, k, maxPts));
    }

    public double new21Game(int n, int k, int maxPts) {
        // 特判：如果 k == 0，直接停止，点数为0，只要 n >= 0 就赢
        if (k == 0) return 1.0;

        // dp[x] 表示从点数 x 开始，最终点数 <= n 的概率
        double[] dp = new double[k + maxPts]; // 最大可能点数是 k-1 + maxPts
        double windowSum = 0.0;

        // 初始化：x >= k 的情况
        for (int x = k; x <= Math.min(n, k + maxPts - 1); x++) {
            dp[x] = 1.0;
            windowSum += dp[x];
        }
        // 注意：x > n 的情况 dp[x] = 0（默认值）

        // 从 k-1 倒推到 0
        for (int x = k - 1; x >= 0; x--) {
            dp[x] = windowSum / maxPts;
            // 滑动窗口更新：加入 dp[x+1]，移除 dp[x+maxPts]
            // 下次抽牌时，x可以抽，x + maxPts不能抽
            windowSum += dp[x] - dp[x + maxPts];
        }

        return dp[0];
    }
}
